#leetcode题目763：划分字母区间

#难度：中等

#方法：贪心

#题目理解：转换成了若干个窗口去合并的问题。每个窗口内包含的字母是相同的，所以只需要找到每个字母的最后一次出现的位置，然后合并窗口即可。
#见image的图解
#中间过程城中使用了56题的解法，合并区间。

# 这个算法的核心思想是区间合并：
# 找到每个字符的区间：记录每个字符第一次和最后一次出现的位置
# 按起始位置排序：将所有区间按起始位置排序
# 合并重叠区间：如果两个区间重叠，就合并它们
# 计算每个区间的长度：返回每个合并后区间的长度


from typing import List
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        """
        划分字母区间
        字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
        返回一个表示每个字符串片段的长度的列表。
        """
        n = len(s)
        
        # 步骤1：找到每个字符的第一次和最后一次出现位置
        char_intervals = {}
        
        for i in range(n):
            char = s[i]
            if char not in char_intervals:
                char_intervals[char] = [i, i]  # [第一次出现, 最后一次出现]
            else:
                char_intervals[char][1] = i  # 更新最后一次出现位置
        
        # 步骤2：将字典值转换为区间列表
        pairs_list = list(char_intervals.values())
        
        # 步骤3：按第一次出现位置排序
        pairs_list.sort(key=lambda x: x[0])
        
        # 步骤4：合并区间
        res = []
        
        if not pairs_list:  # 处理空字符串情况
            return []
        
        # 初始化第一个区间
        l = pairs_list[0][0]
        r = pairs_list[0][1]
        
        for i in range(1, len(pairs_list)):
            new_l = pairs_list[i][0]
            new_r = pairs_list[i][1]
            
            if new_l > r:  # 当前区间与已合并区间不重叠
                res.append(r - l + 1)  # 添加前一个合并区间的长度
                l = new_l  # 开始新的合并区间
                r = new_r
            else:  # 当前区间与已合并区间重叠
                r = max(r, new_r)  # 扩展右边界
        
        res.append(r - l + 1)  # 添加最后一个合并区间的长度
        
    
        return res

#测试数据
s = "ababcbacadefegdehijhklij"
#预期输出：[9,7,8]
solution = Solution()
print(solution.partitionLabels(s))

s = "eccbbbbdec"
#预期输出：[10]
solution = Solution()
print(solution.partitionLabels(s))

